Zápočet 10. 1. 2011

Varianta A

• Napište TS, který rozpoznává následující jazyk: $1^{x+1}01^{x+2}$

• Ukažte, že $f(x):=x!$ je PRF

• Ukažte, že existuje $n$, pro které $W_n=\{k*n|k\in\mathbb{N}\}$. (Pokud použijete nějakou primitivně rekurzivní nebo částečně rekurzivní funkci, zdůvodněte, proč jde o primitivně nebo částečně rekurzivní funkci.)

• Ukažte, že problém existence přípustného řešení 0-1 celočíselného lineárního programování je NP-úplný

Varianta B

• Napište TS, který rozpoznává jazyk $1^{2^x}, x >= 0$. Stačil popis/postup.

• Ukažte, že $2^x, x>=0$ je PRF. (odvození)

• Ukažte, že existuje $n$, pro které $W_n=\{n^k | k \in\mathbb{N}\}$.

• Ukažte, že rozvrhování je NPC.